package com.zyk.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @author zhangsan
 * @date 2021/4/16 10:43
 */
public class C380 {

    // 第一思路, 使用数组, 插入添加排序(O(N)), 删除二分查找O(logN)
    // 题目要求O(1), 那就使用map, 但是map获取随机数的时候肯能出现key不存在的情况, 所以导致多次随机
    //              使用ArrayList, 插入和随机数可以O(1), 但是删除的时候需要线性的时间.
    // 所以使用Map存储, 以及ArrayList记录插入的值, 以便获取结构中的随机数
    static class RandomizedSet {

        HashMap<Integer, Integer> map;
        List<Integer> values;
        int size;

        /**
         * Initialize your data structure here.
         */
        public RandomizedSet() {
            map = new HashMap<>();
            values = new ArrayList<>();
        }

        /**
         * Inserts a value to the set. Returns true if the set did not already contain the specified element.
         */
        public boolean insert(int val) {
            if (map.containsKey(val)) return false;
            map.put(val, size++);
            values.add(val);
            return true;
        }

        /**
         * Removes a value from the set. Returns true if the set contained the specified element.
         */
        public boolean remove(int val) {
            if (map.containsKey(val)) {
                int index = map.get(val);
//                values.remove(index);   // map中其他的index下标都错了, 所以不能直接删
                int lastElement = values.get(--size);
                values.set(index, lastElement);
                map.put(lastElement, index);
                values.remove(size);
                map.remove(val);
                return true;
            }
            return false;
        }

        /**
         * Get a random element from the set.
         */
        public int getRandom() {
            return values.get((int) (Math.random() * size));
        }
    }


    // for test
    public static void main(String[] args) {
        // 初始化一个空的集合。
        RandomizedSet randomSet = new RandomizedSet();

// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
        System.out.println(randomSet.insert(1));

// 返回 false ，表示集合中不存在 2 。
        System.out.println(randomSet.remove(2));

// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
        System.out.println(randomSet.insert(2));

// getRandom 应随机返回 1 或 2 。
        System.out.println(randomSet.getRandom());

// 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
        System.out.println(randomSet.remove(1));

// 2 已在集合中，所以返回 false 。
        System.out.println(randomSet.insert(2));

// 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
        System.out.println(randomSet.getRandom());
    }

}
